package 剑指Offer;

public class Offer51_数组中的逆序对 {
    //全局变量：统计逆序对数量
    private int count;
    //临时数组，存放结果  一定要放在这，如果放在merge方法中，则每次递归都要创建一个数组，会超时！！
    int[] temp;

    public int reversePairs(int[] a) {
        count = 0;
        temp = new int[a.length];
        MergeSort(a);
        return count;
    }

    private void MergeSort(int[] a) {
        Sort(a, 0, a.length - 1);
    }

    //拆分
    private void Sort(int[] a, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        //二路归并要俩Sort
        Sort(a, left, mid);
        Sort(a, mid + 1, right);
        merge(a, left, mid, right);
    }

    //合并
    private void merge(int[] a, int left, int mid, int right) {
        int k = left;//存放指针
        //左右边界指针
        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                temp[k++] = a[p1++];
            } else {
                /*左边大于右边：为逆序，当大于时，
                表示左区间i及i之后的数都将大于j指向的数，所以出现了mid+1-i个逆序对*/
                //增加的一行代码，用来统计逆序对个数
                count = count + (mid - p1 + 1);
                temp[k++] = a[p2++];
            }
        }
        //左右还有剩余的就直接拼接上
        while (p1 <= mid) {
            temp[k++] = a[p1++];
        }
        while (p2 <= right) {
            temp[k++] = a[p2++];
        }
        //存放回原数组
        for (int i = left; i <= right; i++) {
            a[i] = temp[i];
        }
    }
}
